package com.qjc.demo.train.binarytree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName: BinarySearchTree
 * @Description:
 * @Author: qjc
 * @Date: 2022/5/1 4:42 PM
 */
public class BinarySearchTree {

    TreeNode root;

    // 插入数据
    public void insertNode(int data) {
        root = insert(root, data);
    }

    // 递归插入节点
    private TreeNode insert(TreeNode node, int data) {
        // 结束条件
        if (node == null) return new TreeNode(data);
        if (data < node.data) {
            // 左孩子
            node.leftChild = insert(node.leftChild, data);
        } else if (data > node.data) {
            // 右孩子
            node.rightChild = insert(node.rightChild, data);
        } else {
            // 自己
            node.data = data;
        }
        return node;
    }

    // 前序遍历
    public static void beforeTraver(TreeNode node) {
        if (node == null) return;
        System.out.println(node.data);
        beforeTraver(node.leftChild);
        beforeTraver(node.rightChild);
    }

    // 中序遍历
    public static void midTraver(TreeNode node) {
        if (node == null) return;
        midTraver(node.leftChild);
        System.out.println(node.data);
        midTraver(node.rightChild);
    }

    // 后序遍历
    public static void afterTraver(TreeNode node) {
        if (node == null) return;
        afterTraver(node.leftChild);
        afterTraver(node.rightChild);
        System.out.println(node.data);
    }

    // 广度优先遍历
    public static void levelTraver(TreeNode node) {
        // 新建队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            TreeNode treeNode = queue.poll();
            System.out.println(treeNode.data);
            if (treeNode.leftChild != null) {
                queue.offer(treeNode.leftChild);
            }
            if (treeNode.rightChild != null) {
                queue.offer(treeNode.rightChild);
            }
        }
    }

    public static void main(String[] args) {

        BinarySearchTree bst = new BinarySearchTree();
        bst.insertNode(10);
        bst.insertNode(8);
        bst.insertNode(11);
        bst.insertNode(7);
        bst.insertNode(9);
        bst.insertNode(12);
        /**               10
         *            /       \
         *           8        11
         *        /    \        \
         *       7     9        12
         */
        TreeNode root = bst.root;
        beforeTraver(root);
        System.out.println("-----------");
        midTraver(root);
        System.out.println("-----------");
        afterTraver(root);
        System.out.println("-----------");
        levelTraver(root);

    }

}
